package com.cn.codebrush.数组.回溯;

import java.util.*;

/**
 * @Author Boolean
 * @Date 2022/5/28 19:05
 * @Version 1.0
 */
public class No39组合总和 {

    public static void main(String[] args) {
        System.out.println(combinationSum(new int[]{2,3,6,7},7));
        //System.out.println(combinationSum(new int[]{2,3,5},8));
    }


    static List result = new ArrayList();
    public  static List<List<Integer>> combinationSum(int[] candidates, int target) {
        combinationSumHelper(candidates,target,new ArrayList<>(),0);
        return result;

    }

    public static  void combinationSumHelper(int[] candidates, int target, List<Integer> list,int q) {
        int sum = 0;
        for(int k:list){
            sum = sum + k;
        }

        if(sum > target){
            return;
        }else if(sum == target){
            result.add(new ArrayList<>(list));
            return;
        }

        for(int i=q;i<candidates.length;i++){
            list.add(candidates[i]);
            combinationSumHelper(candidates,target,list,i);
            list.remove(list.size()-1);

        }
    }



    /**
     * 解法一
     */
    /*static Set reslist = new HashSet();
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        combinationSumHelper(candidates,target,new ArrayList());
        return new ArrayList<>(reslist);
    }

    public static void combinationSumHelper(int[] candidates, int target,List list) {
        int n = candidates.length;
        if(target == 0){
            List sonList = new ArrayList(list);
            Collections.sort(sonList);
            reslist.add(sonList);
            return;
        }
        if(target < 0){
            return;
        }

        for(int i=0;i<n;i++){
            list.add(candidates[i]);
            combinationSumHelper(candidates,target-candidates[i],list);
            list.remove(list.size()-1);
        }
    }*/
}
